0% completed
Problem Statement
Given the root of a binary tree, return the bottom-up level order traversal of its nodes' values. (i.e., the lowest level comes first in left to right order.)
Examples
Example 1
- Input: root = [1, 2, 3, 4, 5, 6, 7]
- Expected Output: [[4, 5, 6, 7], [2, 3], [1]]
- Justification:
- The third level has
4,5,6, and7nodes. - The second level has
2and3nodes. - The first level has a single node with the value
1.
- The third level has
Example 2
- Input: root = [12, 7, 1, null, 9, 10, 5]
- Expected Output: [[9, 10, 5], [7, 1], [12]]
- Justification:
- The third level has
9,10, and5nodes. - The second level has
7and1nodes. - The first level has a single node with the value
12.
- The third level has
Example 3
- Input: root = [6,5,2,null,null,1,6,3,56,3]
- Expected Output: [[3,56,3],[1,6],[5,2],[6]]
- Justification:
- The fourth level has
3,56, and3nodes. - The third level has
1, and6nodes. - The second level has
5and2nodes. - The first level has a single node with the value
6.
- The fourth level has
Constraints:
- The number of nodes in the tree is in the range
[0, 2000]. -1000 <= Node.val <= 1000
Solution
To solve the reverse level order traversal problem, we will perform a breadth-first search (BFS) using a queue. The idea is to traverse the tree level by level from top to bottom but store each level's result in reverse order. At each level, we process all nodes, add their values to the current level list, and then enqueue their left and right children. Instead of appending the level at the end of the result, we insert it at the beginning, ensuring that when we finish, the result is in reverse level order.
Step-by-Step Algorithm
-
Initialization:
- If the root is
null, return an empty list because there is no tree to traverse. - Initialize a queue to help with the BFS traversal. The queue will store nodes that need to be processed.
- Initialize an empty list
resultto store the final reversed level order traversal.
- If the root is
-
Start BFS Traversal:
- Add the root node to the queue. This represents the starting point of the level order traversal.
-
Process Nodes Level by Level:
- While the queue is not empty, do the following:
- Find out how many nodes are on the current level by checking the size of the queue (
levelSize = queue.size()). - Initialize an empty list
currentLevelto store the values of the nodes at this level.
- Find out how many nodes are on the current level by checking the size of the queue (
- While the queue is not empty, do the following:
-
Process Each Node in the Current Level:
- For each node at the current level, repeat the following steps:
- Dequeue the front node of the queue.
- Add the value of the node to the
currentLevellist. - If the dequeued node has a left child, enqueue the left child.
- If the dequeued node has a right child, enqueue the right child.
- For each node at the current level, repeat the following steps:
-
Add the Current Level to the Result:
- Once all nodes at the current level have been processed, add the
currentLevellist to the front of theresultlist. This ensures that the levels are inserted in reverse order.
- Once all nodes at the current level have been processed, add the
-
Repeat:
- Repeat the process until all nodes have been processed and the queue is empty.
-
Return the Final Result:
- After processing all the levels, return the
resultlist, which contains the node values in reverse level order.
- After processing all the levels, return the
Algorithm Walkthrough
Input: root = [12, 7, 1, null, 9, 10, 5]
-
Initialization:
- Root: 12
- Initialize
queue = [12] - Initialize
result = []
-
First Level:
levelSize = 1(only one node at this level: 12)- Initialize
currentLevel = [] - Dequeue
12, add its value tocurrentLevel:currentLevel = [12] - Enqueue the left child (
7) and right child (1):queue = [7, 1] - Insert
currentLevelat the beginning ofresult:result = [[12]]
-
Second Level:
levelSize = 2(two nodes at this level: 7 and 1)- Initialize
currentLevel = [] - Dequeue
7, add its value tocurrentLevel:currentLevel = [7] - Enqueue the right child (
9), no left child:queue = [1, 9] - Dequeue
1, add its value tocurrentLevel:currentLevel = [7, 1] - Enqueue the left child (
10) and right child (5):queue = [9, 10, 5] - Insert
currentLevelat the beginning ofresult:result = [[7, 1], [12]]
-
Third Level:
levelSize = 3(three nodes at this level: 9, 10, and 5)- Initialize
currentLevel = [] - Dequeue
9, add its value tocurrentLevel:currentLevel = [9] - Dequeue
10, add its value tocurrentLevel:currentLevel = [9, 10] - Dequeue
5, add its value tocurrentLevel:currentLevel = [9, 10, 5] - No more children to enqueue:
queue = [] - Insert
currentLevelat the beginning ofresult:result = [[9, 10, 5], [7, 1], [12]]
-
Final Result:
- The queue is now empty, so we return the
result. - The final reverse level order traversal is
[[9, 10, 5], [7, 1], [12]].
- The queue is now empty, so we return the
Final Output:
- The reverse level order traversal for the tree
[12, 7, 1, null, 9, 10, 5]is[[9, 10, 5], [7, 1], [12]].
Code
Time Complexity
The time complexity of the above algorithm is
Space Complexity
The space complexity of the above algorithm will be
On this page
Problem Statement
Examples
Solution
Step-by-Step Algorithm
Algorithm Walkthrough
Final Output:
Code
Time Complexity
Space Complexity